import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-08-12
 * Time: 22:06
 */

public class Solution {
    /**
     *  方法一: 求出两个数的所有公因子
     *  从大到小进行测试
     */
    public static String gcdOfStrings(String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        List<Integer> commonDivisors = findCommonDivisors(len1, len2);
        Collections.sort(commonDivisors, (o1, o2)->o2-o1);
        for (Integer div: commonDivisors) {
            boolean flag = true;
            String s = str1.substring(0, div);
            for (int i = div;i < len1;i += div) {
                if (!str1.substring(i, i+div).equals(s)) {
                    flag = false;
                    break;
                }
            }
            // str1 不能被整除
            if (!flag) {
                continue;
            }
            for (int i = 0;i < len2;i += div) {
                if (!str2.substring(i, i+div).equals(s)) {
                    flag = false;
                    break;
                }
            }
            // 两个都能被整除
            if (flag) {
                return s;
            }
        }
        return "";
    }

    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    public static ArrayList<Integer> findCommonDivisors(int a, int b) {
        int gcdValue = gcd(a, b);
        ArrayList<Integer> commonDivisors = new ArrayList<>();
        commonDivisors.add(gcdValue);
        for (int i = 1; i * i <= gcdValue; i++) {
            if (gcdValue % i == 0) {
                commonDivisors.add(i);

                if (i != gcdValue / i) {
                    commonDivisors.add(gcdValue / i);
                }
            }
        }
        return commonDivisors;
    }


    /**
     *  方法二: 只需比较最大公约数即可
     *  推理: 假如最大长度为 x , 那么 x 一定为 gcd 的因子
     *  因为 两个数的公共因子都是 gcd 的因子
     *  用 x 可以拼接出 s1, s2, 那么 x 也能拼出 s(gcd)
     *  将 x 用 s(gcd) 进行替换得出 s(gcd) 一定能拼出 s1, s2
     *  所以最长的那个一定是 s(gcd)
     *  否则就是 ""
     */
    public String gcdOfStrings2(String str1, String str2) {
        int len1 = str1.length(), len2 = str2.length();
        String T = str1.substring(0, gcd2(len1, len2));
        if (check2(T, str1) && check2(T, str2)) {
            return T;
        }
        return "";
    }

    public boolean check2(String t, String s) {
        int lenx = s.length() / t.length();
        StringBuffer ans = new StringBuffer();
        for (int i = 1; i <= lenx; ++i) {
            ans.append(t);
        }
        return ans.toString().equals(s);
    }

    public int gcd2(int a, int b) {
        int remainder = a % b;
        while (remainder != 0) {
            a = b;
            b = remainder;
            remainder = a % b;
        }
        return b;
    }

    /**
     *  只要 str1 + str2 == str2 + str1
     *  则说明两个字符串一定有最大公共子串
     *  并且我们可以知道如果有公共子串, 那么这个子串长度一定是 gcd(len1, len2);
     *  为什么 str1 + str2 == str2 + str1 就一定有最大公共子串?
     *  必要性: 有公共子串, 那么 str1 + str2 == str2 + str1
     *  充分性: 先将 str1 + str2 以及 str2 + str1 都分割为 一段一段的, 每段长度为 gcd(len1, len2)
     *  ▲▲▲▲▲▲▲ ▲▲▲
     *  0123456 789
     *  ▲▲▲ ▲▲▲▲▲▲▲
     *  abc defghij
     *  两个相等, 那么
     *  0 == a == d == 7 == h == 4 == e == 1 == b == 8 == i == 5 == f == 2 == c == 9 == j == 6 == g == 3
     *  即可以推出来 str1 str2 都可以由  ▲(ss.sub(0, gcd(len1, len2))) 组成
     *  依据就是: ① 上下对应位置相等 ② 字符串相对位置相等
     * @param str1
     * @param str2
     * @return
     */
    public String gcdOfStrings3(String str1, String str2) {
        if (!str1.concat(str2).equals(str2.concat(str1))) {
            return "";
        }
        return str1.substring(0, gcd(str1.length(), str2.length()));
    }



}
